package sorting;

/**
 * Created by Tzachi on 18/10/2014.
 * <p>
 * Time Complexity: O(n*logn)
 * Space Complexity: O(n)
 */
public class MergeSort {

    public static void mergesort(int[] array) {
        int[] tmpArray = new int[array.length];
        mergesortRec(array, tmpArray, 0, array.length - 1);
    }

    public static void mergesortRec(int[] array, int[] helper, int leftIndex, int rightIndex) {
        if (leftIndex < rightIndex) {
            int middleIndex = leftIndex + (rightIndex - leftIndex) / 2;
            // sort left side
            mergesortRec(array, helper, leftIndex, middleIndex);
            // sort right side
            mergesortRec(array, helper, middleIndex + 1, rightIndex);
            // combine both
            merge(array, helper, leftIndex, middleIndex, rightIndex);
        }
    }

    private static void merge(int[] array, int[] helper, int leftIndex, int middleIndex, int rightIndex) {
        System.arraycopy(array, leftIndex, helper, leftIndex, rightIndex - leftIndex + 1);
        int i = leftIndex, k = leftIndex;
        int j = middleIndex + 1;
        while (i <= middleIndex && j <= rightIndex) {
            if (helper[i] <= helper[j]) {
                array[k] = helper[i];
                i++;
            } else {
                array[k] = helper[j];
                j++;
            }
            k++;
        }
        while (i <= middleIndex) {
            array[k] = helper[i];
            i++;
            k++;
        }
        while (j <= rightIndex) {
            array[k] = helper[j];
            j++;
            k++;
        }
    }

    public static void main(String[] args) {
        int[] a = {4,6,2,5,7,4,2,1};
        mergesort(a);
        System.out.println();
    }

}
